Theo các nhà khảo cổ học với những phát hiện mới nhất, ở khu vực Bến Nghè của đảo đã tìm thấy nhiều công cụ đá của con người thời đá cũ cách đây hàng vạn năm. Trong thời gian của những thế kỷ đầu Công nguyên, Cồn Cỏ đã từng là địa bàn cư dân Chămpa đặt chân đến.

Trong khoảng thế kỷ 17 - thế kỷ 18, trên con đường giao lưu buôn bán, cư dân Đại Việt cũng đã coi Cồn Cỏ là một điểm dừng. Những phát hiện khảo cổ học ở khu vực Bến Tranh trong tháng 7 năm 1994 đã ghi nhận điều đó.

Tương truyền rằng, dưới thời nhà Nguyễn, Cồn Cỏ là nơi đầy ải của những người có tội. Ở đây, bộ đội đảo khi khơi một giếng cũ (không rõ được đào từ thời nào) đã tình cờ phát hiện một bộ hài cốt cùng với xích cùm bằng sắt[cần dẫn nguồn].

Huyện Cồn Cỏ được thành lập theo nghị định số 174/2004/NĐ-CP ngày 1 tháng 10 năm 2004, trên cơ sở đảo Cồn Cỏ thuộc xã Vĩnh Quang (nay là thị trấn Cửa Tùng), huyện Vĩnh Linh.[1]

Tỉnh Quảng Trị đã làm lễ ra mắt huyện đảo này ngày 18 tháng 4 năm 2005.

Trong tư liệu và bản đồ hàng hải nước ngoài như An Nam đại quốc họa đồ (1838) hoặc Bản đồ Xiêm và Cochin China (Việt Nam) ( năm 1820-1829) do John Crawfurd vẽ, cồn Cỏ được gọi là Hòn Cổ, Tigris Insula, Tiger's Island, Đảo Cọp, Đảo Hổ.